package com.example.array.doublepointer;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
 *在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
 *
 * 输入："Let's take LeetCode contest"
 * 输出："s'teL ekat edoCteeL tsetnoc"
 *
 */
public class Leetcode557_ReverseWords3 {
    public static void main(String[] args) {
        System.out.println(reverseWords("Let's take LeetCode contest"));
    }

    /**
     *
     * @param s
     * @return
     */
    public static String reverseWords(String s) {
        int len;
        Deque<Character> stack = new LinkedList<>();
        if (s == null || (len = s.length()) == 0) return "";
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch != ' ') {
                stack.push(ch);
            } else {
                while (!stack.isEmpty()) {
                    sb.append(stack.pop());
                }
                sb.append(' ');
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    /**
     * 解法二：使用双指针，原地反转单词
     */
    public static String reverseWords2(String s) {
        if (s == null || s.length() == 0) {//边界检查
            return s;
        }
        char[] chars = s.toCharArray();
        int len = chars.length;
        //指向单词的初始字符
        int start = 0;
        int end = 0;//指向单词的结尾字符或者是终止索引
        //截取单词进行 单词翻转
        for (int i = 0; i < len; i++) {
            if (chars[i] == ' ') {//如果查询到了空格，一个单词结束
                end = i - 1;
                reverse(chars, start, end);
                start = i + 1;//反转单词之后把start指向下一个单词的起始
            } else if (i == len - 1) {//如果查询到了数组最后一个字符，一个单词结束
                reverse(chars, start, len - 1);
            }
        }
        return new String(chars);
    }

    //双指针原地翻转方法，给定反转的源数组，给定起始索引和终止索引
    public static void reverse(char[] s, int start, int end) {
        while (start < end) {//如果起始索引小于终止索引，进行反转
            //交换双指针对应的字符
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            start++;
            end--;
        }
    }
}
